/*
 * @Autor: taobo
 * @Date: 2020-06-08 17:21:21
 * @LastEditTime: 2020-06-08 17:27:58
 */ 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

//考察并查集相关知识点，leetCode 990
class Union_set{
private:
    vector<int> set;
public:
    Union_set(){
        for(int i=0;i<26;++i){
            set.push_back(i);
        }
    }
    int find(int index){
        while(index != set[index]){ //路径压缩
            set[index] = set[set[index]];
            index = set[index];
        }
        return index;
    }
    void union_(int index1,int index2){//添加元素
        set[find(index1)] = set[find(index2)];
    }
};

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        Union_set set;
        for(string& str: equations){//构建并查集
            if(str[1] == '='){
                int i = str[0] - 'a';
                int j = str[3] - 'a';
                set.union_(i,j);
            }
        }
        for(string& str: equations){//检查是否属于同一个并查集
            if(str[1] == '!'){
                int i = str[0] - 'a';
                int j = str[3] - 'a';
                if(set.find(i) == set.find(j)){
                    return false;
                }
            }
        }
        return  true;
    }
};

int main()
{
    Solution obj;
    vector<string> nums;
    nums.push_back("a==b");
    nums.push_back("b!=c");
    nums.push_back("a==c");
    bool f = obj.equationsPossible(nums);
    if(f) cout<< "true\n";
    else cout<< "false\n";
    return 0;
}